package cn.lena.sort;

/**
 * lena
 * 插入排序
 * 2021-03-04
 */
public class InsertSort {

	/*
	 * t直接插入排序
	 * 先将第一个记录看作只有一个记录的有序序列，然后从第二个记录开始，依次将待排序的记录插入到前面的有序序列中，直到全部记录排序完毕。
	 * 在排序过程中，前面的记录序列是已经排好序的，而后面的记录序列为待排序序列。
	 * a ==> 需要排序的数组
	 */
	public int[] directInsertSort(int[] a){
		int tmp;	//用于数组元素交换位置时的临时变量
		int j;
		for(int i=1;i<a.length;i++){		//第一个就是已排序序列中的元素
			if(a[i]<a[i-1]){		//如果当前元素小于已排序最大的数，则该元素应该放在有序序列前面.
				tmp=a[i];
				//寻找元素插入位置
				for(j=i-1;j>=0;j--){		//j指向已排序序列的最后一个//若第i个元素<第j个元素，则第j个元素向后移，j向前移。
					if(tmp<a[j])
						a[j+1]=a[j];
					else break;
				}
				//找到插入元素的位置：第j+1的位置
				a[j+1]=tmp;
			}
		}
		return a;
	}

	/*
	 * t折半插入排序
	 * 在直接插入排序的基础上进行改进，插入元素的时候，将已排序序列采用二分查找的方法，查询插入的位置。
	 * a ==> 需要排序的数组
	 */
	public int[] halfInsertSort(int[] a){
		int low,high,mid;
		for(int i=1;i<a.length;i++){
			low=0;
			high=i-1;	//high指向有序元素的最后一位
			while(low<=high){
				mid=(low+high)/2;
				if(a[i]<a[mid])		//若元素位于低半区，high=mid-1
					high=mid-1;
				else		//若元素位于高半区，low=mid+1
					low=mid+1;
			}
			low=a[i];		//暂存当前需要插入的数字
			//元素向后移动
			for(int j=i;j>high+1;j--){
				a[j]=a[j-1];
			}
			//元素应该插入在high+1的位置
			a[high+1]=low;
		}
		return a;
	}

	/*
	 * t希尔排序
	 * 先按照步长分组，然后组内进行直接插入排序
	 * a ==> 需要排序的数组
	 */
	public int[] shellSort(int[] a){
		for(int gap=a.length/2;gap>0;gap=gap/2){		//gap为步长，即增量。每次步长=原步长/2，直到gap=1，结束循环。
			for(int i=gap;i<a.length;i++){		//一次循环排序一组
				int insertValue=a[i];	//把待插入的数给保存起来
				int insertIndex=i-gap;	//已排序列的最后一位
				//进行直接插入排序。
				while(insertIndex>=0&&insertValue<a[insertIndex]){	//若待插入数<当前已排序列的元素，已排序列元素向后移动
					a[insertIndex+gap]=a[insertIndex];	//将insertIndex元素后移至insertIndex+gap
					insertIndex=insertIndex-gap;	//insertIndex向前移动gap步
				}
				//直到找到insertIndex指向的元素小于插入数，插入数放到下一位，即insertIndex+gap处
				a[insertIndex+gap]=insertValue;
			}
		}
		return a;
	}

}
